package leetcode.剑指offer.前40;

import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2021/7/30 23:07
 * @description：https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/
 */
public class 剑指_40_最小的k个数 {
    @Test
    public void test() {
        Solution solution = new Solution();
        System.out.println(Arrays.toString(solution.getLeastNumbers(new int[]{0,1,2,1}, 2)));
    }

    class Solution {
        public int[] getLeastNumbers(int[] arr, int k) {
            for (int i = (arr.length - 2) / 2; i >= 0; i--) {
                adjust(arr, i, arr.length);
            }
            System.out.println(Arrays.toString(arr));
            int[] ans = new int[k];
            int index = 0;
            for (int i = arr.length - 1; i >= arr.length - k; i--) {
                int temp = arr[i];
                arr[i] = arr[0];
                arr[0] = temp;
                ans[index++] = arr[i];
                adjust(arr, 0, i);
            }
            return ans;
        }

        private void adjust(int[] arr, int parentIndex, int len) {
            int temp = arr[parentIndex];
            int childIndex = parentIndex * 2 + 1;
            while (childIndex < len) {
                if (childIndex + 1 < len && arr[childIndex + 1] < arr[childIndex]) {
                    childIndex++;
                }
                if (temp <= arr[childIndex]) break;
                arr[parentIndex] = arr[childIndex];
                parentIndex = childIndex;
                childIndex = childIndex * 2 + 1;
            }
            arr[parentIndex] = temp;
        }
    }
}
